Chapter 1 Regulaer Language

字符集 $\mathrm{\Sigma }$，字符集上的所有有限字符串 ${\mathrm{\Sigma }}^{\ast }$
空字符串 $\epsilon$，我们一般约定 $\epsilon \notin \mathrm{\Sigma }\wedge \epsilon \in {\mathrm{\Sigma }}^{\ast }$，${\mathrm{\Sigma }}_{\epsilon }=\mathrm{\Sigma }\cup \{\epsilon \}$。
$\mathrm{\Sigma }$ 上的语言 $A$ 是 ${\mathrm{\Sigma }}^{\ast }$ 的一个子集，我们可以定义 ${\mathrm{\Sigma }}^{\ast }$ 上字符串的连接操作并以集合乘法的形式拓展到 $\mathcal{P}({\mathrm{\Sigma }}^{\ast })$ 上得到语言之间的连接操作 $A\cdot B=\{a\cdot b\mid a\in A,b\in B\}$ 和 Kleene 闭包 $A^{\ast }=\{a_1\cdots a_n\mid a_i\in A,n\in \mathbb{N}\}$。

确定性有限自动机 DFA 是五元组 $(Q,\mathrm{\Sigma },\delta ,q_0,F),q_0\in Q,F\subseteq Q,\delta :Q\times \mathrm{\Sigma }\to Q$

• "确定性" 体现在 $q_0$ 唯一开始状态和 $\delta :Q\times \mathrm{\Sigma }\to Q$ 状态转移的唯一性。
• DFA 的状态转移是由输入字符驱动的。

非确定性有限自动机 NFA 是五元组 $(Q,\mathrm{\Sigma },\delta ,q_0,F),q_0\in Q,F\subseteq Q,\delta :Q\times {\mathrm{\Sigma }}_{\epsilon }\to \mathcal{P}(Q)$

• "非确定性" 体现在状态转移可以有多个选择，状态转移可以由 $\epsilon$ 驱动。开始状态唯一与否在 NFA 中是等价的。

NFA 和 DFA 的等价性

• DFA 自动地是一个 NFA
• 构造与 NFA $M$ 等价的 DFA $M^{\prime }$：无 $\epsilon$ 边时，$Q^{\prime }=\mathcal{P}(Q),q_0^{\prime }=\{q_0\},{\delta }^{\prime }:\mathcal{P}(Q)\times \mathrm{\Sigma }\to \mathcal{P}(Q),(\{q_i\},\sigma )\mapsto \bigcup _{i\in I}\delta (q_i,\sigma ),F^{\prime }=\{A\subseteq Q\mid A\cap F\ne \varnothing \}$，用集合运算来囊括所有的选择不确定性。存在 $\epsilon$ 边时，提前合并所有的 $\epsilon$ 连通块，定义 $E(q)=\{p\in Q\mid \mathrm{\exists }{m}_1,m_2,\cdots m_n,m_1=q,m_n=p,m_{i+1}\in \delta (m_i,\epsilon )\}$ 并以并集的形式拓展到 $\mathcal{P}(Q)$ 上，对应地替换 $q_0^{\prime }=E(q_0),{\delta }^{\prime }:(\{q_i\},\sigma )\mapsto \bigcup _{i\in I}E(\delta (q_i,\sigma ))$。

正则语言被定义为可以被 DFA 接受的语言。语言 $A$ 是正则语言，存在 DFA $M$ 识别 $A$，存在 NFA $M^{\prime }$ 识别 $A$，这三个命题等价。

接下通过正则表达式正面地描述正则语言的组成结构。$\mathrm{\Sigma }$ 上的一个语言 $A$ 被正则表达式描述当且仅当下面任一成立

• $A=\{a\},a\in \mathrm{\Sigma }\vee A=\{\epsilon \}\vee A=\varnothing$
• 存在 $\mathrm{\Sigma }$ 上的正则表达式 $R_1,R_2$ 满足 $A=R_1\cup R_2\vee A=R_1\cdot R_2\vee A=R_1^{\ast }$。
  上述完整的拆分过程被称为 $A$ 的正则表达式，也称 $A$ 为正则表达式。

广义非确定性有限自动机 GNFA 是五元组 $(Q,\mathrm{\Sigma },\delta ,q_{\text{start}},q_{\text{accept}})$，要求转移边接受的字符串必须能被某个正则表达式描述 $\delta :(Q\setminus \{q_{\text{accept}}\})\times (Q\setminus \{q_{\text{start}}\})\to \mathcal{R}$

GNFA 和 NFA 的等价性

• GNFA 是 NFA：每一条边都是一个正则表达式，而被正则表达式描述的语言必然能够用 NFA 识别（正则表达式所刻画的语言必然是正则语言），把 GNFA 的边替换为对应的 NFA 即可。
• NFA 是 GNFA：状态转移 $q_i\to q_j$ 的每一条边都是单字符，它们构成一个正则表达式 $\bigcup _{i\in I}\{s_i\}$。构造唯一初态和终态可以通过添加 $\epsilon$ 边解决。

GNFA 可以通过 "状态消去" 操作得到一个等价的但是状态数更少边标签信息更加密集的 GNFA

• 对于非初终状态 $q_{\text{rip}}$，${\delta }^{\prime }(q_i,q_j)=\delta (q_i,q_{\text{rip}})\cdot \delta (q_{\text{rip}},q_{\text{rip}}{)}^{\ast }\cdot \delta (q_{\text{rip}},q_j)\cup \delta (q_i,q_j)$ 仍然是一个正则表达式

$\mathrm{\Sigma }$ 上，语言 $A$ 是正则语言当且仅当存在一个正则表达式描述它

• 这个命题进一步说明 NFA、DFA、正则表达式、正则语言这些概念的本质相同
• "正则语言关于并、连接、Kleene 闭包封闭" 给出了这个命题的必要性
  • 并封闭：NFA $M_1,M_2$ ，构造 NFA $M=(Q_1\cup Q_2,\mathrm{\Sigma },\cdots ,q_0,F_1\cup F_2)$，$q_0$ 向 $q_1,q_2$ 连 $\epsilon$ 边。也可以用 DFA 积构造证明（同时跑两个 DFA）
  • 连接封闭：NFA $M_1,M_2$，$F_1$ 中的所有状态向 $q_2$ 连 $\epsilon$ 边
  • Kleene 闭包封闭：NFA $M_1$，$F_1$ 中的所有状态向 $q_1$ 连 $\epsilon$ 边，由于需要接受 $\epsilon$，$q_0$ 可以取任意 $F_1$ 中元素
• 充分性：对于描述正则语言 $A$ 的一个 GNFA，通过不断进行 "状态消去" 操作最终会得到一个二状态的 GNFA，唯一的边标签给出了$q_{\text{start}}\to q_{\text{accept}}$ 的正则表达式。

泵引理

• 叙述：若 $A$ 正则，存在 $p\in \mathbb{N}$，任意 $s\in A,|s|\ge p$ 都可以写成 $s=xyz$ 的形式满足 $|y|>0,|xy|\le p,\mathrm{\forall }i\in \mathbb{N},x{y}^{i}z\in A$ 成立
• 直觉：任意充分长的正则语言字符串都一定具有循环结构
• 证明：一个 $p$ 状态 DFA 接受 $A$，对于 $s\in A,|s|\ge p$，该 DFA 运行的前 $p$ 步经过状态 $q_0,q_1,\cdots ,q_p$，容斥原理给出 $1\le i<j\le p,q_i=q_j$ 的存在性，取 $x$ 为 $s$ 的 $[0,i)$ 切片，$y$ 为 $[i,j)$ 切片，$z$ 为 $[j,|s|)$ 切片。

Myhill Nerode 定理

• 对于语言 $L\subseteq {\mathrm{\Sigma }}^{\ast }$，在 ${\mathrm{\Sigma }}^{\ast }$ 上定义 Nerode 关系 $x{\equiv }_{L}y\iff \mathrm{\forall }z\in {\mathrm{\Sigma }}^{\ast },xz\in L\leftrightarrow yz\in L$，此时称 $x,y$ 在 $L$ 中不可区分。定义左商 $x^{-1}L=R_x=\{z\in {\mathrm{\Sigma }}^{\ast }\mid xz\in L\}$ 可以重新叙述 Nerode 关系为 $x{\equiv }_{L}y\iff x^{-1}L=y^{-1}L$。用 DFA 语言不严谨地叙述 Nerode 关系：如果存在 DFA $M$ 接受 $L$，在 $M$ 上运行 $x,y$ 结束后位于状态 $q_x,q_y$，那么 $q_x,q_y$ 的可达子图同构（图结构和图状态是否被接受两个意义下的）。
• Nerode 关系是等价关系。
• Nerode 关系满足右不变性 $x{\equiv }_{L}y\Rightarrow \mathrm{\forall }w\in {\mathrm{\Sigma }}^{\ast },xw{\equiv }_{L}yw$。
• 定理叙述：$L\subseteq {\mathrm{\Sigma }}^{\ast }$ 是正则语言等价于 $|{\mathrm{\Sigma }}^{\ast }/{\equiv }_L|<\mathrm{\infty }$。并且如果 $|{\mathrm{\Sigma }}^{\ast }/{\equiv }_L|$ 是识别 $L$ 的 DFA 的最小状态数。
• 证明：
  • 充分性：考虑识别 $L$ 的 DFA $M$，首先拓展 ${\delta }^{\ast }:Q\times {\mathrm{\Sigma }}^{\ast }\to Q$，定义 $f(x)={\delta }^{\ast }(q_0,x)$，成立 $f(x)=f(y)\Rightarrow x{\equiv }_{L}y$（反方向不成立是因为可能存在同构的可达子图），于是我们有映射 $g:Q\to {\mathrm{\Sigma }}^{\ast }/{\equiv }_L,f(x)\mapsto [x{]}_L$，从而 $|{\mathrm{\Sigma }}^{\ast }/{\equiv }_L|\le |\mathrm{Im}(g)|\le |\mathrm{Dom}(g)|=|Q|$。
  • 必要性：构造 DFA $M_L=(Q_L,\mathrm{\Sigma },{\delta }_L,q_L,F_L)$ 满足 $Q_L={\mathrm{\Sigma }}^{\ast }/{\equiv }_L,q_L={\left[\epsilon \right]}_L,\delta ({\left[x\right]}_L,\sigma )={\left[x\sigma \right]}_L,F_L=\{{\left[x\right]}_L\mid x\in L\}$，$\delta$ 的良定义性来自于 Nerode 关系的右不变性，$F_L$ 的良定义性 $\mathrm{\forall }y\in {\left[x\right]}_L,y\in L\iff x\in L$ 是显然的。
  • $M_L$ 恰好识别 $L$：$x$ 被 $M_L$ 接受等价于 ${\delta }_L^{\ast }({\left[\epsilon \right]}_L,x)\in F_L\iff {\left[x\right]}_L\in F_L\iff x\in L$，所以 $\mathcal{L}(M_L)=L$。
• 泵引理中的循环结构出现的原因就是正则语言只能记住有限状态的前缀历史信息，当字符串长度超过前缀历史信息状态数数时就会出现循环。